package com.leetcode.array;

/**
 * 338. 比特位计数 Counting Bits
 *
 * @author haizi
 * @date 2018/11/4
 */
public class CountingBits {

    // 这是个找规律的题目
    // 很难发现偶数n的二进制数1的个数和n/2一样多
    // 很难发现奇数n的二进制数1的个数比n/2多一个
    // 这确实比较难发现
    public int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; i++){
            result[i] = result[i >> 1] + (i&1);
        }

        return result;


    }

}
